package com.cdream.basic.algorithm.leetcode.linkedlist;

/**
 * todo
 *
 * @author cdream
 * @date 6/12/21
 */
public class Question86 {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(2);
        listNode.next = new ListNode(1);
        System.out.println(new Question86().partition(listNode, 2));
    }

    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(-1);
        ListNode dummy2 = new ListNode(-1);

        ListNode dummy1Index = dummy1;
        ListNode dummy2Index = dummy2;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val >= x) {
                dummy1Index.next = cur;
                cur = cur.next;
                dummy1Index = dummy1Index.next;
                dummy1Index.next = null;
            } else {
                dummy2Index.next = cur;
                cur = cur.next;
                dummy2Index = dummy2Index.next;
                dummy2Index.next = null;
            }
        }
        dummy2Index.next = dummy1.next;
        return dummy2.next;
    }
}
